import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import javax.swing.tree.TreeNode;

/**
 * 
 * 路径总和
 * 
 * 给定一个二叉树和一个目标和，确定所有从根到叶子的路径上总和等于目标和的路径。
 * 
 */
public class 路径总和 {
    
    public static void main(String[] args) {
        
        TN root = new TN(5);
        root.left = new TN(4);
        root.right = new TN(8);
        root.left.left = new TN(11);
        root.left.right = new TN(13);
        root.right.left = new TN(4);
        root.right.right = new TN(7);
        root.left.right.left = new TN(2);
        root.left.right.right = new TN(9);


        List<List<Integer>> result = pathSum(root, 20);

        if(result.isEmpty()){
        
            System.out.println("NA");

            return;
        }

        for(List<Integer> subResult : result){

            subResult.stream().map(s -> s+", ").forEach(System.out::print);
            System.out.println();
        }


    }

    private static List<List<Integer>> pathSum(TN root, int sum) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(root, sum, path, result);
        return result;
    }

    private static void dfs(TN node, int remaining, List<Integer> path, List<List<Integer>> result) {
        if (node == null) {
            return;
        }
        path.add(node.val);
        if (node.left == null && node.right == null && remaining == node.val) {
            result.add(new ArrayList<>(path));
        }
        dfs(node.left, remaining - node.val, path, result);
        dfs(node.right, remaining - node.val, path, result);
        path.remove(path.size() - 1);
    }

    private static class TN {

        int val;
        TN left;
        TN right;

        public TN(int val){

            this.val = val;
        }
    }
}
